图2.2 连锁店所在的区域
方格图中的线表示可以行走的道路，相邻两个格点的距离为 1。栋栋要送餐必须走可以行走的道路，而且不能经过红色标注的点。
送餐的主要成本体现在路上所花的时间，每一份餐每走一个单位的距离需要花费 1 块钱。每个客户的需求都可以由栋栋的任意分店配送，每个分店没有配送总量的限制。
现在你得到了栋栋的客户的需求，请问在最优的送餐方式下，送这些餐需要花费多大的成本。
输入格式
输入的第一行包含四个整数 ，分别表示方格图的大小、栋栋的分店数量、客户的数量，以及不能经过的点的数量。
接下来 行，每行两个整数 ，表示栋栋的一个分店在方格图中的横坐标和纵坐标。
接下来 行，每行三个整数 ，分别表示每个客户在方格图中的横坐标、纵坐标和订餐的量。（注意，可能有多个客户在方格图中的同一个位置）
接下来 行，每行两个整数，分别表示每个不能经过的点的横坐标和纵坐标。
输出格式
输出一个整数，表示最优送餐方式下所需要花费的成本。
样例输入 10 2 3 3
1 1
8 8
1 5 1
2 3 3
6 7 2
1 2
2 2
6 8
样例输出 29
评测用例规模与约定
前 30% 的评测用例满足： 。
前 60% 的评测用例满足： 。
所有评测用例都满足： ， 。可能有多个客户在同一个格点上。每个客户的订餐量不超过 1000，每个客户所需要的餐都能被送到。
2
●
题目分析
宽度优先搜索（Breadth First Search，BFS），顾名思义，从初始结点开始逐层向下扩展，在第 层结点还没有全部搜索完之前，不进入第 层结点的搜索。
本题使用 BFS 求所有源点和所有目标点之间的最短距离。注意最后结果超 int 范围要用 long long 定义。
3
●
参考实现
C++实现
*本案例摘自《CCF CSP 认证考试历年真题解》第2章第2节
02
参考书籍
《CCF CSP 认证考试历年真题解》
ISBN：978-7-302-59279-2
中国计算机学会 编著
定价：59元
扫码优惠购书
编辑推荐
如何促进大学的计算机本科教育？如何为企业和研究生教育培养合格的人才？为了解决这些问题，计算机软件专业认证 (Certified Software Professional，CSP) 应运而生。
CSP以上机考试的方式对学生进行考察，能比笔试更真实地反映学生的程序设计语言、算法和实际编程调试能力。此外，CSP的命题由CCF CSP技术委员会组织完成，避免了每个学校题库有限、出题成本高的问题。
自2014年以来，CSP已经开展了23次认证。目前，CSP每年的考生人数在3万人左右，不少CSP高分考生在推荐研究生或找工作方面获得了优先的机会。更重要的是，有越来越多的学校将CSP纳入教学计划，要求毕业生必须在CSP中获得一定的分数才能毕业。这体现了CSP以考促教的初衷。
本题解的出版，为教师教学和学生学习提供了CSP试题的解题思路和标准程序代码，相信能够为大学计算机专业的程序设计相关教学起到促进作用。
内容简介
本书收录了中国计算机学会计算机软件专业认证（Certified Software Professional，CCF CSP）前 10 次认证试题，对这些试题进行了分类，并逐一给出了题目分析和参考实现。
本书既适合高等学校主讲编程语言、算法和数据结构等课程的教师在辅导学生时使用，也适合要提高编程能力，特别是希望到信息技术相关领域求职的人士自学参考。
作者简介
中国计算机学会（China Computer Federation，CCF）成立于1962年，全国一级学会，是中国计算机及相关领域的学术团体，宗旨是为本领域专业人士的学术和职业发展提供服务，推动学术进步和技术成果的应用，引领学术方向，促进技术和产业应用一线的交流和互动。
CCF秉承会员构成、会员治理和服务会员的理念，每年举办几百场次各种规模、层次的学术会议、产业与技术论坛和培训，开展评奖、竞赛、计算机专业工程教育认证、计算机职业资格认证、科学普及、计算机术语审定等系列活动。
03
精彩推荐
CCF CSP历年真题解｜编程进阶
CCF CSP-J/S第一轮认证必考知识点：贪心算法
CCF CSP-J/S第一轮认证必考知识点：回溯算法
CCF CSP-J/S第一轮认证必考知识点：二值图像的最大连通块
CCF CSP-J/S第一轮认证必考知识点：哥德巴赫猜想
CCF CSP-J/S第一轮认证考纲详解
Python 韩信点兵思政案例（含优惠码）
Python ︱爬取天气预报信息（附视频）
《机器学习》实验指导书（附实验参考+代码）
Python爬虫综合实战 │ 创建云起书院爬虫（附代码）
Python爬虫实战 │ Email提醒（附代码）
Python深度学习 │一文掌握卷积神经网络
CCF CSP历年真题解｜编程进阶
CCF CSP-J/S第一轮认证必考知识点：贪心算法
CCF CSP-J/S第一轮认证必考知识点：回溯算法
CCF CSP-J/S第一轮认证必考知识点：二值图像的最大连通块
CCF CSP-J/S第一轮认证必考知识点：哥德巴赫猜想
CCF CSP-J/S第一轮认证考纲详解
Python 韩信点兵思政案例（含优惠码）
Python ︱爬取天气预报信息（附视频）
《机器学习》实验指导书（附实验参考+代码）
Python爬虫综合实战 │ 创建云起书院爬虫（附代码）
Python爬虫实战 │ Email提醒（附代码）
Python深度学习 │一文掌握卷积神经网络 返回搜狐，查看